1876C - Autosynthesis - CodeForces Solution

#include<bits/stdc++.h>

#define rep(i, x, y) for(int i=x;i<=y;i++)
#define per(i, x, y) for(int i=x;i>=y;i--)
using namespace std;
#define dbg(x...) \
    do { \
        std::cout << #x << " -> "; \
        err(x); \
    } while (0)

void err() {
    std::cout << std::endl;
}

template<class T, class... Ts>
void err(T arg, Ts &... args) {
    std::cout << arg << ' ';
    err(args...);
}

const int N = 2e5 + 10;
const int mod = 998244353;
//const int mod = 1e9 + 7;
#define int long long
const int inf = 1e18;

int qmi(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = a * a % mod) {
        if (b & 1)res = res * a % mod;
    }
    return res;
}

int n, vis[N], col[N], a[N];
vector<int> e[N];
bool flag = 1;

void dfs(int u) {
    for (auto v: e[u]) {
        if (col[v]) {
            if (col[v] != 3 - col[u])flag = 0;
        } else col[v] = 3 - col[u], dfs(v);
    }
}

void elysira() {
    cin >> n;
    rep(i, 1, n)cin >> a[i], vis[a[i]]++,e[i].push_back(a[i]);
    queue<int> q;
    rep(i, 1, n)if (!vis[i])q.push(i);
    while (not q.empty()) {
        auto u = q.front();
        q.pop();
        if (!col[a[u]]) {
            if (--vis[a[a[u]]] == 0)q.push(a[a[u]]);
        }
        col[u] = 1, col[a[u]] = 2;
    }
    rep(i, 1, n)if (!col[i])col[i] = 1, dfs(i);
    if (!flag)cout << "-1\n";
    else {
        vector<int> ans;
        rep(i, 1, n)if (col[i] == 1)ans.push_back(a[i]);
        cout << ans.size() << "\n";
        for (auto x: ans)cout << x << " ";
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int tc = 1;
    //cin >> tc;
    for (int i = 1; i <= tc; i++) {
        elysira();
    }
}
/*
*/
/*
*/